package com.leetcode.design;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/10/28 21:12
 */
public class Twitter {

    static class User {
        // 用户ID
        public int userId;
        // 粉丝
        public Map<Integer, User> followers;
        // 关注者
        public Map<Integer, User> followees;
        // 发的推特 -- 最后面的代表最先发的推特
        public List<Tweet> tweets;

        public User(int userId) {
            this.userId = userId;
            followers = new HashMap<>();
            followees = new HashMap<>();
            tweets = new ArrayList<>();
        }
    }

    static class Tweet {
        // 推特ID
        public int tweetId;
        // 用发帖的序号表示
        public long time;
        // 发帖人的ID
        public int userId;

        public Tweet(int tweetId, int userId) {
            this.tweetId = tweetId;
            this.userId = userId;
            time = timer++;
        }
    }

    // 用一个全局时钟作为时间排序
    private static long timer = 0L;

    private Map<Integer, User> users;

    public Twitter() {
        users = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        User user = getUser(userId);
        Tweet tweet = new Tweet(tweetId, userId);
        user.tweets.add(tweet);
    }

    // 多路归并排序
    public List<Integer> getNewsFeed(int userId) {
        User user = getUser(userId);
        Queue<Tweet> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o.time));

        // 临时创建一个Map用来表示关注者
        Map<Integer, User> followees = new HashMap<>(user.followees);

        // 记录坐标每个关注者当前的tweets坐标 index
        Map<Integer, Integer> map = new HashMap<>();

        // 记录每个tweets的坐标, 都是从最先发的推特开始计数
        followees.forEach((id, followee) -> map.put(id, followee.tweets.size() - 1));

        // 多路归并算法在这里做了一个优化
        while (followees.size() > 0) {
            Iterator<Integer> iterator = map.keySet().iterator();
            while (iterator.hasNext()) {
                int id = iterator.next();
                if (!followees.containsKey(id)) {
                    // 减少遍历次数
                    iterator.remove();
                    continue;
                }

                User followee = getUser(id);
                int index = map.get(followee.userId);
                if (index == -1) {
                    // Tweet为空
                    iterator.remove();
                    followees.remove(id);
                    continue;
                }
                Tweet tweet = followee.tweets.get(index);
                if (index == 0) {
                    // 遍历到最后一条twitter
                    followees.remove(id);
                } else {
                    // index 向前移动
                    map.put(followee.userId, index - 1);
                }

                if (queue.size() < 10) {
                    queue.offer(tweet);
                } else {
                    // 进行时间的比较，如果这个人的当前时间比优先队列的时间久，那么在这个index往前的所有tweet时间都会更久
                    // 那么可以将这个tweet用户临时移除本轮遍历的关注者列表，减少遍历次数，优化算法速度
                    Tweet peek = queue.peek();
                    if (peek.time > tweet.time) {
                        followees.remove(tweet.userId);
                    } else  {
                        Tweet poll = queue.poll();
                        queue.offer(tweet);
                        followees.remove(poll.userId);
                    }
                }
            }
        }

        LinkedList<Integer> tweets = new LinkedList<>();
        while (queue.size() > 0) {
            Tweet poll = queue.poll();
            tweets.offerFirst(poll.tweetId);
        }

        return tweets;
    }

    public void follow(int followerId, int followeeId) {
        // 自己关注自己是非法的
        if (followeeId == followerId) {
            return;
        }
        User follower = getUser(followerId);
        User followee = getUser(followeeId);

        followee.followers.put(followerId, follower);
        follower.followees.put(followeeId, followee);
    }

    public void unfollow(int followerId, int followeeId) {
        // 自己取消关注自己是非法的
        if (followeeId == followerId) {
            return;
        }
        User follower = getUser(followerId);
        User followee = getUser(followeeId);

        followee.followers.remove(followerId);
        follower.followees.remove(followeeId);
    }

    // 获取用户的方法，由于有判定操作，所以进行封装
    private User getUser(int userId) {
        if (!users.containsKey(userId)) {
            users.put(userId, new User(userId));
            // 将自己加入关注者
            User user = users.get(userId);
            user.followees.put(userId, user);
        }
        return users.get(userId);
    }

}
